#include<iostream>
using namespace std;
int counter=0;

struct node{
    int key;
    node*leftc=NULL;
    node*rightc=NULL;
};


class binarySearchTree{
private:
    node *root=NULL;
public:
    node* search(node* pointer,int key);
    void insertNode(int value);
    void deltetNodes(node* current);
    void show();
    void printNodes(node* current);
    void search_number(int value);
    void deleteSingleNode(int value);
    node*searchSingleNode(int value);
    ~binarySearchTree();
};

node*binarySearchTree::searchSingleNode(int value){
    node* pointer=root;
    int flag=0;
    while(pointer!=NULL){
        if(pointer->key==value)
        {
            flag=1;
            break;
        }
        else{
            if(pointer->key>value)
                pointer=pointer->leftc;
            else
                pointer=pointer->rightc;
        }
    }
    if(flag)
        return pointer;
    else return NULL;
}

void binarySearchTree::deleteSingleNode(int value){
//    node*target,*tmp;
//    target=tmp=searchSingleNode(value);
//    cout<<endl<<target->key<<endl;
//    if(target!=NULL){
//        if(target->rightc==NULL)
//            target=target->leftc;
//        else if(target->leftc==NULL)
//            target=target->rightc;
//        else{
//            target=tmp->leftc;
//            while(target->rightc!=NULL)
//                target=target->rightc;
//            target->rightc=tmp->rightc;
//            *tmp=*target;
//            tmp=tmp->leftc;
//        }
//         delete target;
//    }
    node*pointer=root,*parent=NULL,*tmp,*p;
    while(pointer->key!=value){
        parent=pointer;
        if(pointer->key>value)
            pointer=pointer->leftc;
        else
            pointer=pointer->rightc;
    }
    if(!pointer){
        cout<<endl<<"no such node!"<<endl;
        return;
    }
//    if(!pointer->rightc)
//        pointer=pointer->leftc;
//    else if(!pointer->leftc)
//        pointer=pointer->rightc;
//    else{
//        tmp=pointer;
//        while(pointer->rightc)
//            pointer=pointer->rightc;
//        pointer->rightc=tmp->rightc;
//        pointer=tmp;
//        tmp=tmp->leftc;
//    }
//    delete pointer;
    if(parent->leftc->key==value){
        if(pointer->rightc==NULL)
            parent->leftc=pointer->leftc;
        else if(pointer->leftc==NULL)
            parent->leftc=pointer->rightc;
        else
        {
            p=pointer;
            tmp=pointer->rightc;
            parent->leftc=pointer->leftc;
            while(pointer->rightc!=NULL)
                pointer=pointer->rightc;
            pointer->rightc=tmp;
            delete p;
        }
    }
    if(parent->rightc->key==value){
        if(pointer->rightc==NULL)
            parent->leftc=pointer->leftc;
        else if(pointer->leftc==NULL)
            parent->leftc=pointer->rightc;
        else{
            p=pointer;
            tmp=pointer->rightc;
            parent->rightc=pointer->leftc;
            while(pointer->rightc!=NULL)
                pointer=pointer->rightc;
            pointer->rightc=tmp;
            delete p;
        }
    }

}


void binarySearchTree::search_number(int value){
    cout<<"number ["<<value<<"] ";
    node *tmp=searchSingleNode(value);
    if(tmp!=NULL)
    {
        cout<<tmp->key<<endl;
        cout<<"IS FOUND"<<endl;
    }
    else
        cout<<"404"<<endl;
}



binarySearchTree::~binarySearchTree(){
    deltetNodes(root);
}
void binarySearchTree::deltetNodes(node *current){
    if(current){
        deltetNodes(current->leftc);
        deltetNodes(current->rightc);
        delete current;
    }
}


void binarySearchTree::show(){
    printNodes(root);
}
void binarySearchTree::printNodes(node *current){
    if(current!=NULL&&counter<20){
        cout<<current->key<<"\t";
        counter++;
        printNodes(current->leftc);
        printNodes(current->rightc);
    }
}

node* binarySearchTree::search(node* pointer,int value){
    node*current=pointer;
    while((pointer!=NULL)&&(current->key!=value))
    {     current=(value<current->key?search(current->leftc,value):search(current->rightc,value));}
    return current;
}


void binarySearchTree::insertNode(int value){
    node* pointer=root,*previous=NULL;
    while(pointer){
        previous=pointer;
        if(value<pointer->key)
            pointer=pointer->leftc;
        else
            pointer=pointer->rightc;
    }
    if(root==NULL){
        root=new node;
        root->key=value;
    }
    else if(value<previous->key)
    {
        previous=previous->leftc=new node;
        previous->key=value;
    }
    else{
        previous=previous->rightc=new node;
        previous->key=value;
    }
}



int main(){
//    string str;
//    cout<<"input 20 nums:  ";
    int num[]={10,8,14,12,19,4,11,18,9,20};
    cout<<endl;
    binarySearchTree bst;
    for(int i=0;i<10;i++)
        bst.insertNode(num[i]);
    bst.show();
    cout<<endl;


    int searchNum;
    cout<<"input searchNum: ";
    cin>>searchNum;
    bst.search_number(searchNum);


    int numberTOdelete;
    while(1){
        cout<<endl<<"input number to delete:  ";
        cin>>numberTOdelete;
        bst.deleteSingleNode(numberTOdelete);
        bst.show();
    }
}
